package leetCode.offer42;

import java.util.Arrays;

public class Solution3 implements Solution{


    /**
     * 这个解法勉强能过，但是时间复杂度还是O(n2)
     * @param nums
     * @return
     */
    @Override
    public int maxSubArray(int[] nums) {

        int max = -Integer.MAX_VALUE;
        int sum = 0;

        for(int i=0;i< nums.length;i++) {
            if(nums[i] >= 0) {
                for(int n = i; n< nums.length;n++) {
                    sum += nums[n];
                    if(sum > max) {
                        max = sum;
                    }
                }
            }
            sum = 0;
        }

        if(max == -Integer.MAX_VALUE){
            Arrays.sort(nums);
            max = nums[nums.length-1];
        }

        return max;

    }

}
